package advance.day02;

import java.util.LinkedList;

/**
 * 描述：
 *      求出所有小于num的子数组的数量，注意：子数组是连续的。
 *      每次遍历确定一个指定左边界的最大子数组（通过构建最大值窗口和最小值窗口，确定最大值和最小值），
 *      然后在该范围内的子数组都是都是满足条件的。
 * @author hl
 * @version 1.0
 * @date 2020/11/5 17:25
 */
public class AlllessNumSubArray {
    public static int getNum(int[] arr, int num){
        if (arr == null) {
            return 0;
        }
        int res = 0;
        int l = 0;
        int r = 0;
        LinkedList<Integer> qmin = new LinkedList<>();
        LinkedList<Integer> qmax = new LinkedList<>();
        while(l < arr.length){
            while(r < arr.length){
                while(!qmin.isEmpty() && arr[qmin.peekFirst()] >= arr[r]){
                    qmin.pollFirst();
                }
                qmin.addLast(r);
                while(!qmax.isEmpty() && arr[qmax.peekFirst()] <= arr[r]){
                    qmax.pollFirst();
                }
                qmax.addLast(r);
                if (qmax.peekFirst() - qmin.peekFirst() > num) {
                    break;
                }
                r++;
            }
            if (qmin.peekFirst() == l) {//判断最小窗口下标是否过期
                qmin.pollFirst();
            }
            if (qmax.peekFirst() == l) {//判断最大窗口小标是否过期
                qmax.pollFirst();
            }
            res += r - l;//以l为左边界，右边界小于r的数组都满足条件
            l++;
        }
        return res;
    }
}
